package com.fanshuai2.niuke.search.dfs;
import java.util.*;

/**
 * 输入int型数组，询问该数组能否分成两组，使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出true；不满足时输出false。
 */
public class Sum2 {
    static boolean canSum(int[] arr) {
        int sum = 0;
        int sum3 = 0;
        int sum5 = 0;

        List<Integer> list = new ArrayList<>();
        for (int a : arr) {
            sum += a;
            if (a % 5 == 0) {
                sum5 += a;
            } else if (a % 3 == 0) {
                sum3 += a;
            } else {
                list.add(a);
            }
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2 - sum3;
        return canSum(list, 0, 0, target);
    }

    static boolean canSum(List<Integer> list, int n, int result, int target) {
        if (n == list.size()) {
            return result == target;
        }

        if (canSum(list, n + 1, result, target)) {
            return true;
        }
        if (canSum(list, n + 1, result + list.get(n), target)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(canSum(arr));

        }
    }
}
